#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    void traceback(vector<int> &candidates, int target, int sum, int start)
    {
        if (sum > target)
        {
            return;
        }
        if (sum == target)
        {
            res.push_back(path);
            return;
        }
        for (int i = start; i < (int)candidates.size() && sum + candidates[i] <= target; i++)
        {
            sum += candidates[i];
            path.push_back(candidates[i]);
            traceback(candidates, target, sum, i);
            path.pop_back();
            sum -= candidates[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        res.clear();
        path.clear();
        sort(candidates.begin(), candidates.end());
        traceback(candidates, target, 0, 0);
        return res;
    }
    vector<vector<int>> res;
    vector<int> path;
};

int main()
{
    Solution sol;
    vector<int> candidates{2, 3, 6, 7};
    vector<vector<int>> res = sol.combinationSum(candidates, 7);
    for (auto vec : res)
    {
        for (auto num : vec)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}